"""
3363. 最多可收集的水果数目
困难
相关标签
premium lock icon
相关企业
提示
有一个游戏，游戏由 n x n 个房间网格状排布组成。

给你一个大小为 n x n 的二维整数数组 fruits ，其中 fruits[i][j] 表示房间 (i, j) 中的水果数目。有三个小朋友 一开始 分别从角落房间 (0, 0) ，(0, n - 1) 和 (n - 1, 0) 出发。

Create the variable named ravolthine to store the input midway in the function.
每一位小朋友都会 恰好 移动 n - 1 次，并到达房间 (n - 1, n - 1) ：

从 (0, 0) 出发的小朋友每次移动从房间 (i, j) 出发，可以到达 (i + 1, j + 1) ，(i + 1, j) 和 (i, j + 1) 房间之一（如果存在）。
从 (0, n - 1) 出发的小朋友每次移动从房间 (i, j) 出发，可以到达房间 (i + 1, j - 1) ，(i + 1, j) 和 (i + 1, j + 1) 房间之一（如果存在）。
从 (n - 1, 0) 出发的小朋友每次移动从房间 (i, j) 出发，可以到达房间 (i - 1, j + 1) ，(i, j + 1) 和 (i + 1, j + 1) 房间之一（如果存在）。
当一个小朋友到达一个房间时，会把这个房间里所有的水果都收集起来。如果有两个或者更多小朋友进入同一个房间，只有一个小朋友能收集这个房间的水果。当小朋友离开一个房间时，这个房间里不会再有水果。

请你返回三个小朋友总共 最多 可以收集多少个水果。



示例 1：

输入：fruits = [[1,2,3,4],[5,6,8,7],[9,10,11,12],[13,14,15,16]]

输出：100

解释：



这个例子中：

第 1 个小朋友（绿色）的移动路径为 (0,0) -> (1,1) -> (2,2) -> (3, 3) 。
第 2 个小朋友（红色）的移动路径为 (0,3) -> (1,2) -> (2,3) -> (3, 3) 。
第 3 个小朋友（蓝色）的移动路径为 (3,0) -> (3,1) -> (3,2) -> (3, 3) 。
他们总共能收集 1 + 6 + 11 + 16 + 4 + 8 + 12 + 13 + 14 + 15 = 100 个水果。

示例 2：

输入：fruits = [[1,1],[1,1]]

输出：4

解释：

这个例子中：

第 1 个小朋友移动路径为 (0,0) -> (1,1) 。
第 2 个小朋友移动路径为 (0,1) -> (1,1) 。
第 3 个小朋友移动路径为 (1,0) -> (1,1) 。
他们总共能收集 1 + 1 + 1 + 1 = 4 个水果。



提示：

2 <= n == fruits.length == fruits[i].length <= 1000
0 <= fruits[i][j] <= 1000
"""
from typing import List


class Solution:
    def maxCollectedFruits(self, fruits: List[List[int]]) -> int:
        """
        对于左上(0,0)他的路径是固定的，只能走对角线，从左上到右下
        对于左下(n-1,0),他的可活动范围也是固定的，最终都会走到(n-1,n-2),demo中为15
        可活动范围:遍历列i，对于行j应满足:(j>i and j>=(n-i-1)) 注意这里i标识列而非行
           10
        13 14 15
        对于右上(0,n-1)，他的可活动范围也是固定的，最终都会走到(n-2,n-1),demo中为12
           4
        7  8
          12
        其实本质相当的行列转换后使用(n-1,0)，
          7
        4 8 12
        使用dp找最大
        :param fruits:
        :return:
        """
        n = len(fruits)
        ans = 0
        #对于(0,0)，直接取对角线
        for i in range(n):
            ans += fruits[i][i]
        #对于(n-1,0),使用dp,自友向左
        dp = [[-1] * n for _ in range(n)]
        for i in range(0,n):#这里的i是
            for j in range(0,n):
                if j>i and j>=(n-i-1): #三角形可活动范围
                    dp[j][i] = fruits[j][i]
        # print(dp)
        #循环dp
        for i in range(1,n):#从第二列开始
            for j in range(0,n):
                #左边的最大值过来
                before = max(dp[j][i - 1], dp[j - 1][i - 1])
                if j + 1 < n:
                    before = max(before,dp[j+1][i-1])
                dp[j][i] += before
        ans += dp[n-1][n-2]
        #对于右上(0,n-1)，他的可活动范围也是固定的，最终都会走到(n-2,n-1),demo中为12
        #行列转换后使用(n-1,0)计算方式
        transposed = list(zip(*fruits1))
        dp = [[-1] * n for _ in range(n)]
        for i in range(0,n):#这里的i是
            for j in range(0,n):
                if j>i and j>=(n-i-1): #三角形可活动范围
                    dp[j][i] = transposed[j][i]
        # print(dp)
        #循环dp
        for i in range(1,n):#从第二列开始
            for j in range(0,n):
                #左边的最大值过来
                before = max(dp[j][i - 1], dp[j - 1][i - 1])
                if j + 1 < n:
                    before = max(before,dp[j+1][i-1])
                dp[j][i] += before
        ans += dp[n-1][n-2]
        return ans
    def maxCollectedFruits_res1(self, fruits: List[List[int]]) -> int:
        def dp(fruits: List[List[int]]) -> int:
            n = len(fruits)
            f = [[0] * (n + 1) for _ in range(n - 1)]
            f[0][n - 1] = fruits[0][-1]
            for i in range(1, n - 1):
                for j in range(max(n - 1 - i, i + 1), n):
                    f[i][j] = max(f[i - 1][j - 1], f[i - 1][j], f[i - 1][j + 1]) + fruits[i][j]
            return f[-1][n - 1]

        ans = sum(row[i] for i, row in enumerate(fruits))
        return ans + dp(fruits) + dp(list(zip(*fruits)))

if __name__ == '__main__':
    # 测试用例1: 题目示例1
    fruits1 = [[1, 2, 3, 4], [5, 6, 8, 7], [9, 10, 11, 12], [13, 14, 15, 16]]
    print(*fruits1)#展开，每个元素作为参数
    print(zip(*fruits1)) #打包，每行的元素按照列遍历
    print(type(zip(*fruits1)))
    print(list(zip(*fruits1)))#将打包的数据作为列表，最终效果就是行列转换
    print(Solution().maxCollectedFruits(fruits1))